{ "metadata": { "kernelspec": { "codemirror_mode": "scheme", "display_name": "Scheme", "language": "scheme", "name": "calico_scheme_kernel" }, "name": "", "signature": "sha256:801c92e3ec1821e5fd5ab8cbd52ada796c84d55399ed788d2b987a9a8914473d" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "heading", "level": 1, "metadata": {}, "source": [ "Fibonacci, recursion, and memoization in Scheme" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We examined the running speed of computing the $n^{th}$ Fibonacci number in Scheme. " ] }, { "cell_type": "code", "collapsed": false, "input": [ "(define fib\n", " (lambda (n)\n", " (if (or (= n 1)\n", " (= n 2))\n", " 1\n", " (+ (fib (- n 1))\n", " (fib (- n 2))))))" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 1 }, { "cell_type": "code", "collapsed": false, "input": [ "(map fib (range 1 11))" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 2, "text": [ "(1 1 2 3 5 8 13 21 34 55)" ] } ], "prompt_number": 2 }, { "cell_type": "markdown", "metadata": {}, "source": [ "How much time does it take to compute?" ] }, { "cell_type": "code", "collapsed": false, "input": [ "%%time\n", "(fib 10)" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "Time: 0.102875947952 seconds.\n", "\n" ] }, { "metadata": {}, "output_type": "pyout", "prompt_number": 3, "text": [ "55" ] } ], "prompt_number": 3 }, { "cell_type": "code", "collapsed": false, "input": [ "%%time\n", "(fib 20)" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "Time: 11.850864172 seconds.\n", "\n" ] }, { "metadata": {}, "output_type": "pyout", "prompt_number": 4, "text": [ "6765" ] } ], "prompt_number": 4 }, { "cell_type": "code", "collapsed": false, "input": [ "(import-as \"calico.widgets\" '*)\n", "(import-as \"calico.display\" 'display)\n", "\n", "(GoogleChart \"LineChart\" '(\"n\" \"Time\")\n", " (map (lambda (n)\n", " (let ((start (current-time)))\n", " (fib n)\n", " (- (current-time) start)))\n", " (range 1 20)))" ], "language": "python", "metadata": {}, "outputs": [ { "html": [ "\n", "
\n", "\n", "" ], "metadata": {}, "output_type": "pyout", "prompt_number": 5, "text": [ "